﻿#pragma once
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace shuaiming_open_address
{
	enum State
	{
		EXIST,// 存在
		EMPTY,// 空
		DELETE// 删除
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}
		size_t size() const { return _n; }
		bool Insert(const pair<K, V>& kv)
		{
			// 不支持键值冗余
			if (Find(kv.first))
				return false;
			// 扩容
			// 用负载因子判断
			if (_n * 10 / _tables.size() >= 7)
			{
				HashTable newhstab;
				// 这里用reserve会导致扩不了容
				newhstab._tables.resize(_tables.size() * 2);
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
						newhstab.Insert(e._kv);
				}
				newhstab._tables.swap(_tables);
			}
			// 插入
		    // key%M（M为哈希表当前可用大小（size））
			size_t hash0 = hs(kv.first) % _tables.size();
			size_t hashi = hash0;
			int i = 1;
			while (_tables[hashi]._state == EXIST)
			{
				hashi = (hash0 + i) % _tables.size();
				++i;
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			++_n;
			return true;
		}
		HashData<K, V>* Find(const K& key)
		{
			size_t hashFind = hs(key) % _tables.size();
			size_t hashFindi = hashFind;
			int i = 1;
			// 删除也要找，因为用了开放地址法的线性探测，可能查找值是在某个删除值的后面
			while (_tables[hashFindi]._state != EMPTY)
			{
				size_t hashKey = hs(_tables[hashFindi]._kv.first);
				// 找到还得判断是否是存在值而非删除值
				if (hashKey == hs(key) && _tables[hashFindi]._state == EXIST)
					return &_tables[hashFindi];
				hashFindi = (hashFind + i) % _tables.size();
				++i;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* find = Find(key);
			if (find)
			{
				find->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
		Hash hs;
	};
}